# 最少交换次数来组合所有1： https://leetcode-cn.com/problems/minimum-swaps-to-group-all-1s-together/（力扣会员可看）

"""
    题目描述： 将所有1组合在一起， 求最小的交换次数。
    例如：
    case1： [1, 0, 1, 0, 1]
    输出： 1
    [1, 1, 1, 0, 0]  交换第二个 0 和最后一个1， 最少需要交换1次

    或者 [0, 0, 1, 1, 1] 也是交换1次，最少

    case2： [0, 0, 0, 1, 0]
    输出： 0
"""

# 这道题我的思路是 ，首先求出来 一共有多少1（假设为k个）， 然后，使用滑动窗口，长度k。 
# 看看滑动窗口内，0的个数越少， 那么，说明交换的次数越少！

class Solution:
    def minSwapNum(self, nums: list) -> int:
        # 1. 计算1的个数，确定滑动窗口长度
        k, n = sum(nums), len(nums)
        i = j = ans = 0
        for j in range(k):
            if nums[j] == 0: ans += 1

        ZeroCnt = ans
        j += 1
        while j < n:
            if nums[j] == 0: ZeroCnt += 1
            if nums[i] == 0: ZeroCnt -= 1
            i += 1
            j += 1
            ans = min(ZeroCnt, ans)
        
        return ans

            
nums = [1, 0, 1, 0, 1]
nums = [0, 0, 0, 1, 0]

s = Solution()
rst = s.minSwapNum(nums)
print(rst)


